0.无约束优化问题
问题形式:
对一个无约束问题,是一个局部极小值的必要条件是:
一阶必要条件,在处取得0梯度:
二阶必要条件,在该点处黑塞矩阵(Hessian)半正定:
,
是任意的非零向量。
是向量 关于黑塞矩阵
的二次型。
不等式
表示二次型是半正定的,也就是说,对于任何非零向量 ,二次型的值都大于等于零。
Hessian矩阵的正定性在判断优化算法可行性时非常有用,简单地说,黑塞矩阵正定,则
函数的二阶偏导数恒 > 0
函数的变化率(斜率)即一阶导数始终处于递增状态
函数为凸
1.等式约束问题
问题形式:
举例:
1.1 感性角度
上述问题可视化如下:
图中左上角的橙色点处,往哪里走达到约束下的最小值?
假设是无约束优化问题,我们知道直接往目标函数负梯度方向走,就可以到达最小
但是现在有一个等式的约束,只能在约束(实际上就是图中的橙色圆)上移动,在圆上移动只能沿着切线方向移动,只要保证每次移动都满足移动方向和目标函数负梯度方向夹角小于90°,就是在向极小值移动!
当移动...
1. 凸集
1.1 凸集 convex set
等价条件:
对于任意的与任意的有
解析:
当 时, 等于 ;当 时,公式等于 。表示从点 到点 的线段,当 在
范围内变化时,会在这条线段上取得各个点,形成一条直线。
表明:凸集合中两点的连线仍然属于该集合
推广等价条件:
对于任意的有
1.2 常见凸集
超平面hyperplane:
半空间halfspace:
多面体polyhedra:
线性等式刻画的也是多面体,因:
2. 凸组合与凸包
2.1 凸组合 convex combination
拓展一下:
线性组合:,啥限制条件都没有
仿射组合:,
非负组合:,
凸组合:,即仿射组合+非负组合
2.2 凸包 convex hull of set C
注意:凸包是相对于集合来说的,尽管这个集合可能并不是凸集
凸包就是将原集合的补充成一个凸集
参考
https://www.bilibili.com/video/BV1rE411H7P6
1.Windows环境配置
Git https://git-scm.com/
Node https://nodejs.org/en
Pandoc https://pandoc.org/
2.安装Hexo
12345678910npm config set registry https://registry.npmmirror.comnpm install -g hexo-clinpm install --save hexo-deployer-git# 本地测试hexo init # 初始化博客hexo generate # 申城网站信息hexo server # 开始网站服务
3.Github仓库
在你的github中新建仓库“username.github.io”,其中,username就是你注册时使用的用户名。
修改你博客根目录下的_config.yml文件中的deploy配置项:
1234deploy: type: git repository: git@github.com:username/username.github.io.git ...
1.基本思想
逻辑回归是一种广义上的线性回归分析模型,简单来看就是将线性回归的结果y通过一个映射函数sigmoid映射到0-1区间,将sigmoid函数输出当做概率值,当概率值大于0.5时分类为正类,反之反类。
2.模型
其中,映射函数sigmoid :
3.推导过程
3.1 表示正/负类概率
逻辑回归是二分类算法,定义 正类标签为,负类标签为。
这里既然是定义,说明是人为规定的,原因在于这样定义对后续的推导可以起到简化作用,后文紧接着会提到。如果你比较叛逆,不这样定义也是可以的,就是推导会非常麻烦。
接下来是第二个涉及定义的地方,定义将sigmoid函数输出为概率值,sigmoid函数输出是[0,1]区间的,恰好符合概率的要求。且定义正类的概率为,负类自然就是。
综上,
则给定一些特征,其是正类的概率写作
或 ;负类的概率写作 或
关键一步的化繁为简,将分类为正类的概率 和
分类为负类的概率 同时用一条公式表达出来:
令合并令原式变换为
非常非常巧妙是不是,自己尝试代入标签y=1或者y=0看看效果是不是...
1.原理
1.1 闭式
模型:
损失函数:
目标:
说明:
正规方程形式求解,即为直接求 的最小值:
先展开 :
对 进行求导:
令 得:
上述结果即为求解结果,需要说明的是:特征矩阵𝑿不满秩(即存在特征间的线性相关性),则正规方程求解过程中的矩阵求逆操作可能会导致数值不稳定性。
1.2 梯度下降
模型:
注:表示的第维
损失函数:
注:表示第个样本
目标:
说明:
损失函数
是一个关于参数 的二次型,对
进行展开:
对
进行偏微分求导运算得到:
每次根据梯度更新参数:
梯度下降法步骤:
2.Python实现
2.0 导包
123456789101112# 导入所需的包import numpy as npimport pandas as pdimport matplotlib.pyplot as pltimport seaborn as snsfrom sklearn.impute import SimpleImputerfrom sklearn.prepro...
1.原理分析
OPT:
选择在未来最长时间内不会被使用的页面进行淘汰。可以理论上得到最优的页面置换方案,缺页率最低。但其需要预知未来,无法实现,故仅可以作为“标尺”来衡量页面置换算法的优劣性。
FIFO:
选择最先进入内存的页面进行淘汰。其实现简单,但是会出现Belady异常。
LRU:
选择最近最少使用的页面进行淘汰。避免了Belady异常,缺页率表现比FIFO要更好。LRU算法是对“过去”的总结,通过过去的经验来预测未来的页面访问序列。但是在当内存容量较小时,LRU算法可能出现大量缺页的情况Thrashing即抖动。
我尝试在不同数量的数据块下测试上述三种算法,并且作出不同数量内存块(3-9)下三种算法的命中率曲线图(使用gunplot)
使用指导书给的测试文件测试结果如下:
可以看出FIFO的曲线非常曲折,LRU的曲线较光滑相对接近最光滑的OPT曲线。在命中率方面可以看出OPT>FIFO>LRU。
2.代码实现
三种算法的实现如下:
1234567891011121314151617181920212223242526272...